package test

import (
	"fmt"
	"math"
	"sort"
)

func Xinghuan1(n, e, d int) int {
	//n,e,d:=0,0,0
	//fmt.Scan(&n,&e,&d)
	var f func(n, e, d, s int) int
	f = func(n, e, d, s int) int {
		if n <= 0 || e < s*s {
			return -1
		}
		res := 0
		t := e / (s * s)
		if d <= s*t {
			return d / s
		}

		for k := 1; k <= 10; k++ {
			tmp := f(n-1, e-s*t, d-s*t, k)
			if tmp == -1 {
				continue
			} else {
				if res == 0 || tmp+t < res {
					res = tmp + t
				}
			}
		}
		if res == 0 {
			return -1
		}
		return res
	}
	res := math.MaxInt32
	for s := 1; s <= 10; s++ {
		tmp := f(n, e, d, s)
		if tmp < res && tmp > 0 {
			res = tmp
		}
	}
	if res == math.MaxInt32 {
		res = 0
	}
	return res
}

func Xinghuan2(i int) {
	//i:=0
	//fmt.Scan(&i)
	res := 0
	cnt := 1
	cntall := 0
loop:
	for cntall < i {
		for j := 1; j <= cnt; j++ {
			cntall++
			if cntall == i {
				res = j
				break loop
			}
		}
		cnt++
	}
	fmt.Println(res)
}

func Coin(coins []int) int {
	sort.Ints(coins)
	var f func(int, int)
	res := 0
	f = func(target, index int) {
		if index == len(coins) {
			return
		}
		//1要index
		res += findEqualCoins(coins[index+1:], target+coins[index], 0, 0)
		f(target+coins[index],index+1)
		//1不要index
		res += findEqualCoins(coins[index+1:], target, 0, 0)
		f(target,index+1)
	}
	f(0, 0)
	return res
}

func findEqualCoins(coins []int, target, sum int, index int) int {
	if target==0{
		return 0
	}
	if index == len(coins) {
		if target == sum {
			return 1
		}
		return 0
	}
	if target < sum {
		return 0
	}
	if target == sum {
		return 1
	}
	return findEqualCoins(coins, target, sum+coins[index], index+1) +
		findEqualCoins(coins, target, sum, index+1)
}
